﻿//-----------------------------------------------------------------------------------------------------------
// WBFSSync Project by Omega Frost 
// http://wbfssync.codeplex.com/
//
// WBFSSync is Licensed under the terms of the 
// Microsoft Reciprocal License (Ms-RL)
//-----------------------------------------------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace WBFSe3.IO
{
    //-------------------------------------------------------------------------------------------------------
    //
    //-------------------------------------------------------------------------------------------------------
    public static class WbfsSearch
    {
        //---------------------------------------------------------------------------------------------------
        // Directory tree node class
        //---------------------------------------------------------------------------------------------------
        private class TreeNode
        {
            //-----------------------------------------------------------------------------------------------
            // Constants
            //-----------------------------------------------------------------------------------------------
            public const int RszCount = 8;


            //-----------------------------------------------------------------------------------------------
            // Variables
            //-----------------------------------------------------------------------------------------------
            public String Name;
            public TreeNode[] Nodes;
            public WbfsFileInfo[] Files;
            public int NumNodes;
            public int NumFiles;


            //-----------------------------------------------------------------------------------------------
            // Routines
            //-----------------------------------------------------------------------------------------------

            //-----------------------------------------------------------------------------------------------
            // Constructor
            //-----------------------------------------------------------------------------------------------
            public TreeNode(String name)
            {
                this.Name = name;
                this.Nodes = null;
                this.Files = null;
                this.NumNodes = 0;
                this.NumFiles = 0;
            }


            //-----------------------------------------------------------------------------------------------
            // Searches for a file
            //-----------------------------------------------------------------------------------------------
            public WbfsFileInfo SearchFile(String path, int start)
            {
                TreeNode current = WalkDown(path, ref start);
                if (current == this) return null;

                //Check if only the filename remained
                if (path.IndexOf('\\', start) > 0)
                    return null;

                //Check if the path belongs to a WbfsFileInfo
                String file = path.Substring(start);
                for (int i = 0; i < current.NumFiles; i++)
                {
                    if (current.Files[i].FileNames.ContainsFileName(file))
                        return current.Files[i];
                }

                return null;
            }


            //-----------------------------------------------------------------------------------------------
            // Searches for a node
            //-----------------------------------------------------------------------------------------------
            public TreeNode SearchNode(String path, ref int start, bool roundToNearest)
            {
                TreeNode current = WalkDown(path, ref start);
                
                //Check if the whole path was traversed
                if (start == path.Length)
                {
                    return current;
                }
                else
                {
                    if (!roundToNearest)
                        return Root;

                    for (int i = 0; i < current.NumNodes; i++)
                    {
                        int n;
                        if ((n = CrossPaths(current.Nodes[i].Name, 0, path, start)) > 0)
                        {
                            start += n;
                            return current.Nodes[i];
                        }
                    }

                    return current;
                }
            }


            //-----------------------------------------------------------------------------------------------
            // Inserts a directory
            //-----------------------------------------------------------------------------------------------
            public TreeNode InsertDirectory(String dir)
            {
                int start = 0;
                TreeNode current = WalkDown(dir, ref start);

                //Find shared path
                for (int i = 0; i < current.NumNodes; i++)
                {
                    //Search for subpart matches
                    int l = CrossPaths(dir, start, current.Nodes[i].Name, 0);
                    if (l == 0) continue;

                    if (l + start == dir.Length)
                    {
                        //Create the new node
                        TreeNode oldnode = current.Nodes[i];
                        TreeNode newnode = new TreeNode(dir.Substring(start, l));

                        //Change the old node
                        oldnode.Name = oldnode.Name.Substring(l);

                        //Swap the nodes
                        current.Nodes[i] = newnode;
                        newnode.AppendNode(oldnode);
                        return newnode;
                    }
                    else
                    {
                        //Create an intermediate node and the new node
                        TreeNode oldnode = current.Nodes[i];
                        TreeNode newnode = new TreeNode(dir.Substring(start + l));
                        TreeNode intermediate = new TreeNode(dir.Substring(start, l));

                        //Change the old node
                        oldnode.Name = oldnode.Name.Substring(l);

                        //Setup intermediate
                        intermediate.AppendNode(oldnode);
                        intermediate.AppendNode(newnode);

                        //Replace the i'th node
                        current.Nodes[i] = intermediate;
                        return newnode;
                    }
                }

                //No shared path, insert new
                return current.AppendNode(new TreeNode(dir.Substring(start)));
            }


            //-----------------------------------------------------------------------------------------------
            // Appends a file to the node
            //-----------------------------------------------------------------------------------------------
            public WbfsFileInfo AppendFile(WbfsFileInfo file)
            {
                if ((this.Files == null) || (this.NumFiles == this.Files.Length))
                    Array.Resize(ref this.Files, this.NumFiles + RszCount);

                return (this.Files[this.NumFiles++] = file);
            }


            //-----------------------------------------------------------------------------------------------
            // Appends a subnode to the node
            //-----------------------------------------------------------------------------------------------
            public TreeNode AppendNode(TreeNode node)
            {
                if ((this.Nodes == null) || (this.NumNodes == this.Nodes.Length))
                    Array.Resize(ref this.Nodes, this.NumNodes + RszCount);

                return (this.Nodes[this.NumNodes++] = node);
            }


            //-----------------------------------------------------------------------------------------------
            // Removes a file from the node
            //-----------------------------------------------------------------------------------------------
            public void RemoveFile(WbfsFileInfo file)
            {
                int i;
                for (i = 0; i < this.NumFiles; i++)
                {
                    if (this.Files[i] == file)
                    {
                        this.NumFiles--;
                        this.Files[i] = this.Files[this.NumFiles];
                        this.Files[this.NumFiles] = null;
                    }
                }
            }


            //-----------------------------------------------------------------------------------------------
            // Check how many tokens on both strings are equal
            //-----------------------------------------------------------------------------------------------
            public int CrossPaths(String patha, int starta, String pathb, int startb)
            {
                int finallen = 0;

                do
                {
                    int pa = patha.IndexOf('\\', starta) + 1;
                    int pb = pathb.IndexOf('\\', startb) + 1;

                    if (pa - starta != pb - startb)
                        break;

                    if (String.CompareOrdinal(patha, starta,
                        pathb, startb, pa - starta) != 0)
                        break;

                    finallen += pa - starta;
                    starta = pa;
                    startb = pb;

                } while ((starta != patha.Length) && (startb != pathb.Length));

                return finallen;
            }


            //-----------------------------------------------------------------------------------------------
            // Returns the current node's matching subnode
            //-----------------------------------------------------------------------------------------------
            public TreeNode WalkDown(String path, ref int start)
            {
                TreeNode current = this;

            NODESEARCH:
                for (int i = 0; i < current.NumNodes; i++)
                {
                    if (IsContained(current.Nodes[i].Name, 0, path, start))
                    {
                        current = current.Nodes[i];
                        start += current.Name.Length;
                        goto NODESEARCH;
                    }
                }

                return current;
            }
            
            
            //-----------------------------------------------------------------------------------------------
            // Count files in a branch
            //-----------------------------------------------------------------------------------------------
            public int RecursiveCountFiles()
            {
                int n = 0;
                for (int i = 0; i < this.NumNodes; i++)
                    n += this.Nodes[i].RecursiveCountFiles();
                
                return n + this.NumFiles;
            }


            //-----------------------------------------------------------------------------------------------
            // Returns all the files in a brench
            //-----------------------------------------------------------------------------------------------
            public void RecursiveGetFiles(ref WbfsFileInfo[] files, ref int index)
            {
                if (files.Length < index + this.NumFiles)
                    Array.Resize(ref files, index + this.NumFiles + 3 * RszCount);

                if (this.Files != null)
                    Array.Copy(this.Files, 0, files, index, this.NumFiles);

                index += this.NumFiles;

                for (int i = 0; i < this.NumNodes; i++)
                    this.Nodes[i].RecursiveGetFiles(ref files, ref index);
            }


            //-----------------------------------------------------------------------------------------------
            // Checks if a is contained in b
            //-----------------------------------------------------------------------------------------------
            public Boolean IsContained(String a, int starta, String b, int startb)
            {
                if (a.Length - starta > b.Length - startb)
                    return false;

                int runto = a.Length - starta;
                for (int i = 0; i < runto; i++)
                {
                    if (a[starta + i] != b[startb + i])
                        return false;
                }

                return true;
            }


            //-----------------------------------------------------------------------------------------------
            // Override for debug
            //-----------------------------------------------------------------------------------------------
            public override string ToString()
            {
                return this.Name;
            }
        }


        //---------------------------------------------------------------------------------------------------
        // Constants / Control variables
        //---------------------------------------------------------------------------------------------------
        private const int RszCount = 8;
        internal static Boolean GameOnly = true;


        //---------------------------------------------------------------------------------------------------
        // Variables
        //---------------------------------------------------------------------------------------------------
        private static ReaderWriterLock Lock = new ReaderWriterLock();
        private static TreeNode Root = new TreeNode(".");
        private static WbfsFileInfo[] FileList = null;
        private static int NumFiles = 0;


        //---------------------------------------------------------------------------------------------------
        // Properties
        //---------------------------------------------------------------------------------------------------

        public static int IndexedFiles
        {
            get
            {
                return NumFiles;
            }
        }


        //---------------------------------------------------------------------------------------------------
        // Adds a file to cache
        //---------------------------------------------------------------------------------------------------
        internal static void AddFile(WbfsFileInfo file)
        {
            //Gain access for reading
            Lock.AcquireReaderLock(-1);

            //Search the node
            int start = 0;
            String path = file.FileNames.Path;
            TreeNode node = Root.SearchNode(path, ref start, false);

            //Change to write permission
            Lock.UpgradeToWriterLock(-1);

            //Insert the file in the tree
            if (node == Root) node = Root.InsertDirectory(path);
            node.AppendFile(file);

            //Insert the file in the array
            if ((FileList == null) || (FileList.Length == NumFiles))
                Array.Resize(ref FileList, NumFiles + RszCount);

            file.index = NumFiles;
            FileList[NumFiles++] = file;

            //Release the lock
            Lock.ReleaseLock();
        }


        //---------------------------------------------------------------------------------------------------
        // Removes a file from the cache
        //---------------------------------------------------------------------------------------------------
        internal static void RemoveFile(WbfsFileInfo file)
        {
            //Gain access for editing the tree
            Lock.AcquireWriterLock(-1);

            //Search and remove the node
            int start = 0;
            TreeNode node = Root.SearchNode(file.FileNames.Path, ref start, false);
            node.RemoveFile(file);

            //Remove from the main list
            NumFiles--;
            FileList[file.index] = FileList[NumFiles];
            FileList[file.index].index = file.index;
            file.index = -1;

            //Release the lock
            Lock.ReleaseLock();
        }


        //---------------------------------------------------------------------------------------------------
        // Returns all files in a directory or branch
        //---------------------------------------------------------------------------------------------------
        public static WbfsFileInfo[] GetFiles(String path, bool subdirectories)
        {
            if (!path.EndsWith("\\"))
                path += '\\';

            // Gain access for reading the tree
            Lock.AcquireReaderLock(-1);

            int start = 0;
            WbfsFileInfo[] files;
            TreeNode t = Root.SearchNode(path, ref start, subdirectories);

            if (start == path.Length)
            {
                if (subdirectories)
                {
                    int count = 0;
                    files = new WbfsFileInfo[RszCount];
                    t.RecursiveGetFiles(ref files, ref count);

                    if (files.Length != count)
                        Array.Resize(ref files, count);
                }
                else
                {
                    files = new WbfsFileInfo[t.NumFiles];
                    Array.Copy(t.Files, files, t.NumFiles);
                }
            }
            else
            {
                files = new WbfsFileInfo[0];
            }

            // Release the lock
            Lock.ReleaseLock();

            return files;
        }


        //---------------------------------------------------------------------------------------------------
        // Counts the number of files in a directory or branch
        //---------------------------------------------------------------------------------------------------
        public static int CountFiles(String path, bool subdirectories)
        {
            if (!path.EndsWith("\\"))
                path += '\\';

            // Gain access for reading the tree
            Lock.AcquireReaderLock(-1);

            int start = 0, count = 0;
            TreeNode t = Root.SearchNode(path, ref start, subdirectories);
            if (start == path.Length)
            {
                count = t.RecursiveCountFiles();
            }

            // Release the lock
            Lock.ReleaseLock();

            return count;
        }


        //---------------------------------------------------------------------------------------------------
        // Removes the already built files from the array and return them
        //---------------------------------------------------------------------------------------------------
        public static WbfsFileInfo[] GetIndexed(WbfsPath directory)
        {
            List<WbfsFileInfo> lfiles =
                new List<WbfsFileInfo>();

            // Gain access for reading the tree
            Lock.AcquireReaderLock(-1);

            int start = 0;
            TreeNode node = Root.WalkDown(directory.Path, ref start);

            // Check for full path match
            if (directory.Path.IndexOf('\\', start) >= 0)
                goto END;

            for (int i = 0; i < node.NumFiles; i++)
            {
                // Get the file
                WbfsFileInfo file = node.Files[i];

                // Keep the disc updated
                if (file.State == WbfsFileState.NotUpdated)
                    file.Update();

                // Do not consider invalid files
                WbfsFileState state = file.State;
                if ((state != WbfsFileState.Ok) && (state != WbfsFileState.Temporary))
                    continue;

                for (int j = 0; j < file.FileNames.Count; j++)
                {
                    int idx = Array.IndexOf(directory.Files,
                        file.FileNames.Files[j]);
                    if (idx >= 0)
                    {
                        directory.Files[idx] = null;
                    }
                }

                // Append the file to the destination
                lfiles.Add(file);
            }

        END:

            //Release the lock
            Lock.ReleaseLock();

            return lfiles.ToArray();
        }


        //---------------------------------------------------------------------------------------------------
        // Searches for a specific file
        //---------------------------------------------------------------------------------------------------
        public static WbfsFileInfo SearchFile(String file)
        {
            WbfsFileInfo f;

            //Gain access for reading the tree
            Lock.AcquireReaderLock(-1);

            f = Root.SearchFile(file, 0);

            //Release the lock
            Lock.ReleaseLock();

            return f;
        }


        //---------------------------------------------------------------------------------------------------
        // Searches for a pattern
        //---------------------------------------------------------------------------------------------------
        public static WbfsFileInfo[] Search(String str)
        {
            Lock.AcquireReaderLock(-1);

            // LinQ S2 lol
            str = str.ToLower();
            var found = from f in FileList
                        where f.ToString().ToLower().Contains(str)
                        select f;

            Lock.ReleaseLock();
            return found.ToArray();
        }
    }
}
